package ch01;

/**
 * Implement a method to perform basic string compression using the counts
 * of repeated characters. For example, the string aabcccccaaa would become
 * a2blc5a3. If the "compressed" string would not become smaller than the 
 * original string, your method should return the original string.
 * 
 * @author Xi Chen
 *
 */

public class CompressString_05 {
	
	public static String compressString(String s) {
		StringBuffer sb = new StringBuffer();
		int cnt = 1; // The number of continuous same characters
		for (int i = 0; i < s.length() - 1;) { // O(n)
			int j = i + 1;
			while (s.charAt(i) == s.charAt(j)) {
				cnt++;
				if (++j > s.length() - 1) { // Pay attention here
					break;
				}
			}
			sb.append(s.charAt(i));
			sb.append(cnt);
			cnt = 1;
			i = j;
		}
		return (sb.length() < s.length() ? sb.toString() : s);
	}

	public static void main(String[] args) {
		String s = "aabcccccaaa";
		String s1 = "abcdefggg";
		System.out.println(s1);
		System.out.println(compressString(s1));
	}

}
